class Solution {
    public int ans;
    public int m;
    public int n;
    public boolean[][] fg;
    public int uniquePaths(int m_, int n_) {
        m=m_;
        n=n_;
        fg=new boolean[m][n];
        dfs(0,0);
        return ans;
    }

    private void dfs(int a, int b) {
        if(a==m-1 && b==n-1){
            ans++;
            return ;
        }
        //向下移动
        if(check(a+1,b) && !fg[a+1][b]){
            fg[a+1][b]=true;
            dfs(a+1,b);
            fg[a+1][b]=false;
        }
        //向右移动
        if(check(a,b+1) && !fg[a][b+1]){
            fg[a][b+1]=true;
            dfs(a,b+1);
            fg[a][b+1]=false;
        }
    }

    private boolean check(int i,int j){
        return i>=0 && i<m && j>=0 && j<n;
    }
}